package com.placedial;

import java.io.IOException;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Set;

public class KB {
	
	  private Helper help=new Helper();
	  private GraphP returnGp=null;   
	
	  public void boundSearchTree(GraphP root) throws IOException{
			
			this.runKernalization(root);
			if(root.getK()>=0&&root.getSize()==0){
				this.returnGp=root;
				return ;
			}

				
			if(root.getK()<=0&&root.getSize()>0){
				
				return ;
				
			}
			
			if(root.getK()<0&&root.getSize()==0){
				return;
			}
			
			HashMap rt=root.getGraph();
			//select one vertex 
			String vertex="";
			Set set =rt.keySet();
			Iterator kit=set.iterator();
			
			vertex=(String) kit.next();
			
			
			GraphP leftChild=help.copy(root);
			
			//remove vertex
			this.removeV(vertex, leftChild);
			this.runKernalization(leftChild);
			
			boundSearchTree(leftChild);
			
			GraphP rightChild=help.copy(root);
			this.removeAdv(vertex, rightChild);
			this.runKernalization(rightChild);
			
			boundSearchTree(rightChild);
			
				
				
		
			
			
		}


	public void removeAdv(String v,GraphP gp){
		  
		  //add neghours into coverset
		  Set coverset=gp.getCoverSet();
		  int k=gp.getK();
		  int size=gp.getSize();
		  
		  HashMap graph=gp.getGraph();
		  
		  //find neghbours
		  Set negb=(Set)graph.get(v);
		  Set tempSet=help.copySet(negb);
		  
		  for(Object o:tempSet){
			  coverset.add(o);
			  k=k-1;
			  
			  
			  //find  o's neghbours and remove edges with o;
			  Set on=(Set) graph.get(o);
			  Set tempon=help.copySet(on);
			  
			  for(Object n:tempon){
				  //neghours edges
				  Set ne=(Set) graph.get(n);
				  ne.remove(o);
				  graph.put(n, ne);
			  }
			  graph.remove(o);
			  size=size-1;
			  
		  }
		  
		  gp.setCoverSet(coverset);
		  gp.setVertexset(gp.getGraph().keySet());
		  gp.setK(k);
		  gp.setSize(size);
		  gp.setGraph(graph);
		  
		
	}

	public void removeV(String v,GraphP gp){
		
		
		int k=gp.getK();
		Set set=(Set) gp.getGraph().get(v);
		//remove adjecent edges
		for(Object o:set){
			Set ajSet=(Set) gp.getGraph().get(o);
			Set temp=help.copySet(ajSet);
			 temp.remove(v);
			 gp.getGraph().put(o, temp);
		}
		//remove v vertex
		gp.getGraph().remove(v);
		
		gp.setSize(gp.getGraph().size());
		gp.setVertexset(gp.getGraph().keySet());
		gp.getCoverSet().add(v);
		gp.setK(k-1);
	   
		
	}


	public void runKernalization(GraphP gp) throws IOException{
		
		//use temp1 and temp2 record graph size.
		//if temp1 equals temp2 after apply kernaliztion
		//which means we do not need apply again and this recursive process halt
		int temp1=gp.getSize();
		
		this.applyKernalization(gp);
		
		int temp2=gp.getSize();
		if(gp.getK()>0&&temp1!=temp2){
			runKernalization(gp);
			
			
			
		}
		
		
		
		
		
	}




	public void applyKernalization(GraphP gp) throws IOException{
		
		Set vertexset=gp.getVertexset();
		Set coverSet=gp.getCoverSet();
		int k=gp.getK();
		int size=gp.getSize();
		HashMap graph=gp.getGraph();  
	    Set copyVSet=help.copySet(vertexset)  ; 
		   
	    
		    for(Object v:copyVSet){
	      	 if(k>0&&graph.containsKey(v)){ 
		   
		    
		    String key=(String) v;
		    Set adjSet=(Set) graph.get(key);
		    //Iterator adjIt=adjSet.iterator();
		    
	     	//1. search for isolate vertex;
		      if(adjSet.isEmpty()){
		    	graph.remove(key);
		    	
		    	size=size-1;
		    	
		      }
		    //2.search for degree one vertex;
		      if(adjSet.size()==1){
		    	 Iterator ajit=adjSet.iterator();
		    	 String neighbour=(String) ajit.next();
		    	 coverSet.add(neighbour);
	    		 Set nSet=(Set) graph.get(neighbour);
	    		 
	    		 if(!nSet.isEmpty()){
	    			 for(Object incident : nSet){
		    			 Set tempSet=(Set) graph.get(incident);
		    			 tempSet.remove(neighbour);
		    			 graph.put((String) incident, tempSet);
		    		 }
	    		 }
	    		 
	    		 
	    		 graph.remove(neighbour);
	    		
	    		 k=k-1;
	    		 size=size-1;
	    		 
	    		 
		      }
		      
		    //3.search for vertex whose degree >k;
		      if(adjSet.size()>k){
		    	  coverSet.add(key);
		    	  Set kSet=(Set) graph.get(key);
		    	  
		    	  for(Object u: kSet){
		    		  Set uSet=(Set) graph.get(u);
		    		  //Set tempUset=this.copySet(uSet);
		    		  uSet.remove(key);
		    		 graph.put((String) u, uSet);
		    	  }
		    	  
		    	  graph.remove(key);
		    	  
		    	  
		    	  k=k-1;
		    	  size=size-1;
		      }
		    	
		    	
		    }
		    
	       }
		   
		   //remove isolate vertex
		    this.removeIsoV(graph, size);
		   
		   gp.setCoverSet(coverSet);
		   gp.setGraph(graph);
		   gp.setK(k);
		   gp.setSize(graph.size());
		   gp.setVertexset(graph.keySet());
		    
		
		
		
		 
		 
		 
	}



	public void removeIsoV(HashMap graph,int size){
		Set kset=graph.keySet();
		Set copykset=help.copySet(kset);
		for(Object o: copykset){
			Set vset=(Set) graph.get(o);
			if(vset.isEmpty()){
				graph.remove(o);
				size=size-1;
			}
		}
	}


	public GraphP getReturnGp() {
		return returnGp;
	}


	public void setReturnGp(GraphP returnGp) {
		this.returnGp = returnGp;
	}


   

}
